package cn.xaut.字符串;

/**
 * 647. 回文子串
 */
public class demo647 {

    static boolean isPalindrome(String s) {

        if (s.length() < 2)
            return true;

        int i = 0, j = s.length() - 1;
        char[] cs = s.toCharArray();
        while (i < j) {
            if (cs[i] != cs[j])
                return false;
            i++;
            j--;
        }
        return true;
    }

    // 暴力解法
    public int countSubstrings(String s) {

        int len = s.length(), count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                if (isPalindrome(s.substring(i, j)))
                    count++;
            }
        }
        return count;
    }

    // 动态规划解法
    public int countSubstrings2(String s) {

        int len = s.length();
        // dp[i][j] 表示 s[i...j] 是否为回文串
        boolean[][] dp = new boolean[len][len];
        char[] cs = s.toCharArray();
        // dp数组的初始化
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j)
                    dp[i][j] = true;
                else if (i + 1 == j)
                    dp[i][j] = cs[i] == cs[j];
                else
                    dp[i][j] = cs[i] == cs[j] && dp[i + 1][j - 1];
            }
        }

        int count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if (dp[i][j])
                    count++;
            }
        }
        return count;
    }

    // 中心扩展法
    public int countSubstrings3(String s) {
        
        int len = s.length(), count = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i < len; i++) { // 遍历每一个中心点

            // j == 0 表示 中心点为一个字符
            // j == 1 表示 中心点为两个字符
            for (int j = 0; j < 2; j++) {
                int l = i, r = i + j;
                while ( (l >= 0 && r < len) && cs[l] == cs[r] ) {
                    count++;
                    l --;
                    r ++;
                }
            }
        }
        
        return count;
    }

    public static void main(String[] args) {

        System.out.println(new demo647().countSubstrings3("abc"));  // 3
        System.out.println(new demo647().countSubstrings3("aaa"));  // 6
    }
}
